class Solution:
    """
    分治法
    """
    def my_pow(self, x: float, n: int):
        # 判断特殊情况：n<0,则应该求1/x的正n次方
        if n < 0:
            n, x = -n, 1 / x
        return self.half_pow(x, n)

    def half_pow(self, x: float, n: int):
        # 退出递归条件
        if n == 0:
            return 1.0
        # 递归解决子问题
        # 踩坑：因为退出条件为n=0，所以递归分治时，子问题必须为n // 2而不是n / 2,否则会陷入死递归
        half = self.half_pow(x, n // 2)
        # 奇数需要在合并前多乘一个x
        return half * half if n % 2 == 0 else half * half * x
